package practioce;

import java.util.LinkedList;

/**
 * create by Sun
 * 2018/9/1
 */
public class huanyuanshu {
    char c;
    huanyuanshu lc;
    huanyuanshu rc;

    static huanyuanshu qz(String s,String d){
        if(s.length()==0){
            return null;
        }
        int index=0;
        for(int i=0;i<d.length();i++){
            if(d.charAt(i)==s.charAt(0)){
                index=i;

                break;
            }
        }
        huanyuanshu tree=new huanyuanshu();
        tree.c=s.charAt(0);

        tree.lc=qz(s.substring(1,index+1),d.substring(0,index));
        tree.rc=qz(s.substring(index+1,s.length()),d.substring(index+1,d.length()));


        return tree;
    }
    static huanyuanshu hoxu(String d,String l){
        if (d.length()==0){
            return null;
        }
        int index=0;
        for(int i=0;i<d.length();i++){
            if(  l.charAt(l.length()-1)==d.charAt(i)){
                index=i;
                break;
            }

        }

        huanyuanshu tree=new huanyuanshu();
        tree.c=l.charAt(index);

        tree.lc=hoxu(d.substring(0,index),l.substring(0,index));
        tree.rc=hoxu(d.substring(index+1),l.substring(index,l.length()-1));

        return tree;



    }
    static int shendu(huanyuanshu tree){
        if(tree!=null){
           int ld=shendu(tree.lc);
           int rd=shendu(tree.rc);
           return ld>rd?ld+1:rd+1;
        }
        return 0;
    }
    static String cengsi(huanyuanshu tree){
        LinkedList<huanyuanshu> list=new LinkedList<>();
        StringBuilder sb=new StringBuilder();
        list.add(tree);

        while (list.size()!=0){
            huanyuanshu h=list.pop();
            sb.append(h.c);
            if(h.lc!=null)
                list.add(h.lc);
            if (h.rc!=null)
                list.add(h.rc);
        }


        return sb.toString();




    }
    public static void main(String[] args) {
        String a="GDAFEMHZ";
        String b="ADEFGHMZ";
        String c="AEFDHZMG";
        huanyuanshu tree=qz(a,b);
        huanyuanshu tree1=hoxu(b,c);
        System.out.println(shendu(tree));
        System.out.println(shendu(tree1));
        System.out.println(cengsi(tree));
      //  LinkedList<Integer> linkedList=new LinkedList<>();
//        linkedList.add(1);
//        linkedList.add(2);
//        linkedList.add(3);
//        linkedList.push(4);
//        linkedList.push(5);
//        linkedList.push(6);
//        //Integer pop = linkedList.pop();
//        System.out.println(linkedList);
//       // Integer poll = linkedList.poll();
//        Integer pop = linkedList.pop();
//        Integer peek = linkedList.peek();
//        System.out.println(pop+" "+linkedList.size());


    }
}
